Notation: We follow [P25] and write $\mathbb{G}$ with multiplicative notation.

Remark and Notation:

• We can assume that the exponents $(d_1,\ldots, d_n)\in\mathbb{F}^n\cap \mathbb{Z}^n$.

• We denote by $m$ the bit-length of the exponents $d_i$; we can assume that these are picked uniformly at random in $\mathbb{F}$ and consider $m=\lceil\log_2(|\mathbb{F}|)\rceil$.

Remark:

• Recall that each $d_{i,j}\in\{0,1\}$, therefore we have MSMs with trivial scalars.

• Provided the $w_j$’s, we can compute $\mathbf{v}^\mathbf{d}$ with $m$ multiplications and $m$ squarings as

  $$\prod_{j=0}^{m−1}w_j^{2^j}=w_0\cdot (w_1\cdot ( w_2\cdots(w_{m-2}\cdot w_{m-1}^{2})^2\cdots )^2)^2;$$

  Note that this resembles Horner’s method for evaluating a polynomial (https://en.wikipedia.org/wiki/Horner%27s_method):

  $$a_0+a_1x+a_2x^2+a_3x^3+\cdots +a_nx^n \\ =a_0+x(a_1+x(a_2+x(a_3+\cdots+x(a_{n−1}+xa_n)))).$$

Notation: Let $\lambda$ be a security parameter.

Assumption 0:

Assumption 1:

Assumption 2:

Assumption 3:

Protocol: Delegated Partial MSM — $\Pi_{MSM}$

Prover $\mathsf{P}$ and Verifier $\mathsf{V}$ input:

Output:

1. $\mathsf{P}$ computes, for each $i=1,\ldots,n$:

   $$d_i=d_{i,0}+2\cdot d_{i,1}+\ldots+2^{m-1}\cdot d_{i,m-1}.$$

2. $\mathsf{P}$ computes, for each $j=1,\ldots,m$:

   $$w_{j}=\prod_{i=1}^{n}v_i^{d_{i,j}}.$$

3. $\mathsf{P}$ sends $\mathsf{V}$ the values $w_{j},\, j=0,\ldots,m-1$.

4. $\mathsf{V}$ chooses $m$ random coefficients $r_0,\ldots,r_{m-1}\in\{0,1\}^{m\times \lambda}$ (that is, $m$ number of $\lambda$-bits).

5. $\mathsf{V}$ computes the length-$m$ MSM with exponents of $\lambda$ bits:

   $$w' := \prod_{j=0}^{m−1}w_j^{r_j}.$$

6. $\mathsf{V}$ computes the length-$n$ MSM with exponents of $\lambda+\log_2m$ bits:

   $$w'' := \prod_{i=1}^{n}v_i^{\sum_{j=0}^{m-1}r_j\cdot d_{i,j}}.$$

7. $\mathsf{V}$ checks

   $$w'=w'',$$

   and if the equality holds, returns $\mathsf{True}$. Otherwise, it returns $\mathsf{False}$.

Proposition (Completeness):

The protocol $\Pi_{MSM}$ is complete.

• Proof:

  It is enough to notice (again) that

  $$\mathbf{v}^\mathbf{d}=\prod_{i=1}^{n}v_i^{d_i}=\prod_{i=1}^{n}v_i^{\sum_{j=0}^{m-1}2^jd_{i,j}}=\prod_{i=1}^{n}\prod_{j=0}^{m-1}v_i^{2^jd_{i,j}} =\prod_{j=0}^{m-1}\prod_{i=1}^{n}v_i^{2^jd_{i,j}}=\prod_{j=0}^{m-1}\left(\prod_{i=1}^{n}v_i^{d_{i,j}}\right)^{2^j} =\prod_{j=0}^{m-1}w_j^{2^j}.$$

  $\blacksquare$

Lemma:

Given a group $(\mathbb{G},1,\cdot)$, what is the probability that a product of $m$, uniformly picked at random group elements is the unit $1$? It is

• Proof:

  We proceed on induction on $m$.

  • If $m=1$, the claim is trivial and equality holds.

  • Similarly, for $m=2$, the claim is obtained from the fact that there exists a unique inverse for each group element. Equality holds.

  • Let us assume the claim for $m-1$ and prove it for $m$.

    Now, the probability, by Bayes’ Theorem, is

    $$\Pr\left[\,\prod_{j=0}^{m-1}g_j = 1 \,\middle|\, g_j\gets_{\$} \mathbb{G}\, \right] \leq \Pr\left[\,g_0\cdot G = 1 \,\land\, G = \prod_{j=1}^{m-1}g_j\,\middle|\, g_j\gets_{\$} \mathbb{G}\,\right] = \Pr\left[\,g_0\cdot G = 1 \,\middle|\, g_j\gets_{\$} \mathbb{G}\,\land\, G = \prod_{j=1}^{m-1}g_j\,\right]\cdot \Pr\left[\,G = \prod_{j=1}^{m-1}g_j\,\middle|\, g_j\gets_{\$} \mathbb{G}\,\right] = \Pr\left[\,g_0\cdot G = 1 \,\middle|\, g_0,G\gets_{\$} \mathbb{G}\,\right]\cdot \Pr\left[\,G = \prod_{j=1}^{m-1}g_j\,\middle|\, g_j\gets_{\$} \mathbb{G}\,\right] \leq \frac{1}{|\mathbb{G}|}\cdot 1.$$

    $\blacksquare$

Lemma:

In the protocol $\Pi_{MSM}$, provided that the random values $r_0,\ldots,r_{m-1}$ are independent, the probability that the quantities $w'$ and $w''$ are equal given that not all $w_i$ values are computed correctly is

• Proof:

  We can write

  $$w''=\prod_{i=1}^{n}v_i^{\sum_{j=0}^{m-1}r_j\cdot d_{i,j}}=\prod_{i=1}^{n}\prod_{j=0}^{m-1}v_i^{r_j\cdot d_{i,j}} =\prod_{j=0}^{m-1}\prod_{i=1}^{n}v_i^{r_j\cdot d_{i,j}}=\prod_{j=0}^{m-1}\left(\prod_{i=1}^{n}v_i^{d_{i,j}}\right)^{r_j},$$

  and compare it with $w'=\prod_{j=0}^{m-1}w_j^{r_j}$.

  Now, suppose that there exists a $j$ such that $w_j\neq \prod_{i=1}^{n}v_i^{d_{i,j}}$; WLOG we can fix $j=0$. Since $\mathbb{G}$ is a group we can write:

  $$w'=w'' \iff 1=w'\cdot (w'')^{-1} = \prod_{j=0}^{m-1}\left(w_j\cdot\left(\prod_{i=1}^{n}v_i^{d_{i,j}}\right)^{-1}\right)^{r_j}\\ \iff 1 = \left(w_0\cdot\left(\prod_{i=1}^{n}v_i^{d_{i,0}}\right)^{-1} \right)^{r_0} \cdot \prod_{j=1}^{m-1}\left(w_j\cdot \left(\prod_{i=1}^{n}v_i^{d_{i,j}}\right)^{-1}\right)^{ r_j} \in \mathbb{G}.$$

  Therefore, written $g_j:=\left(w_j\cdot \left(\prod_{i=1}^{n}v_i^{d_{i,j}}\right)^{-1}\right)^{ r_j} \in \mathbb{G}$, we can apply the above Lemma , since

  • $g_0^{-r_j}= w_j\cdot \left(\prod_{i=1}^{n}v_i^{d_{i,j}}\right)^{-1}\neq 1$, by hypothesis, and therefore, its (unique) inverse is non-trivial;

  • we can assume that the $g_j$ are independent since the $r_j$ are;

  • since the group has order without small factors as in (one can consider prime order) and the exponents have at most $\lambda<m$ bits, $g_0\neq 1$ (and therefore, its unique inverse is non-trivial).

  Therefore we have

  $$\Pr\left[\, w'=w''\, \middle|\, \exists\, j\in\{0,\ldots,m-1\}:w_j\neq \prod_{i=1}^{n}v_i^{d_{i,j}}\,\right]\leq \Pr\left[\prod_{j=0}^{m-1}g_j = 1 | g_j\gets_{\$} \mathbb{G} \right] \leq \frac{1}{|\mathbb{G}|}= 2^{-m}\leq 2^{-\lambda}.$$

  $\blacksquare$

Proposition:

The protocol $\Pi_{MSM}$ is sound.

• Proof:

  The soundness is proved by the above Lemma, with soundness error $2^{-\lambda}$.

  $\blacksquare$

The selected random exponents $r_0,\ldots,r_{m−1}$ are independent and provided by the verifier.

Remark (Question):

In terms of R1CS constraints, is a length-$n$ MSM with exponents of $\lambda+\log_2(m)$ bits cheaper than a length-$n$ MSM with exponents of $m$ bits if $\lambda+\log_2(m) < m$.